# source:https://leetcode.cn/problems/maximum-number-of-coins-you-can-get/ 贪心
class Solution:
    def maxCoins(self, piles: List[int]) -> int:
        piles.sort(reverse=True)
        ans = 0
        n = len(piles)//3
        i = 1
        while n:
            ans += piles[i]
            n -= 1
            i += 2
        return ans

# source:https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles/ 记忆化搜索 动态规划
class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int, j: int) -> int:
            if i < 0:
                return 0
            # 不选这一组中的任何物品
            res = dfs(i - 1, j)
            # 手动计算前缀和
            prefix_sum = 0
            for w in range(min(len(piles[i]), j)):  # 遍历选的数量
                prefix_sum += piles[i][w]
                res = max(res, dfs(i - 1, j - (w + 1)) + prefix_sum)
            return res
        return dfs(len(piles) - 1, k)

# DP:
class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        f = [[0] * (k + 1) for _ in range(len(piles) + 1)]
        for i, pile in enumerate(piles):
            for j in range(k + 1):
                # 不选这一组中的任何物品
                f[i + 1][j] = f[i][j]
                pre = 0
                # 枚举选哪个
                for w in range(min(len(pile), j)):
                    pre += pile[w]
                    f[i+1][j] = max(f[i+1][j], f[i][j-(w+1)]+pre)
        return f[-1][k]